This specification relates to k Nearest Neighbor (k NN) queries in spatial networks.
Recent advances in online map services and their wide deployment in hand-held devices and car-navigation systems have led to extensive use of location-based services. The most popular class of such services is k-nearest neighbor (k NN) queries where users search for geographical points of interests (e.g., restaurants, hospitals) and the corresponding directions and travel-times to these locations. Accordingly, numerous algorithms have been developed (e.g., Hanan Samet and Jagan Sankaranarayanan and Houman Alborzi. Scalable Network Distance Browsing in Spatial Databases. Proceedings of SIGMOD, pages 33-40, Toronto, Canada, 2008; Mohammad Kolandouzan and Cyrus Shahabi. Voronoi-based K NN search in spatial networks. Proceedings of VLDB, pages 840-851, Toronto, Canada, 2004; Dimitris Papadias and Jun Zhang and Nikos Mamoulis and Yufei Tao. Query processing in spatial networks. Proceedings of VLDB, pages 802-813, Berlin, Germany, 2003; Cho, Hyung-Ju and Chung, Chin-Wan. An efficient and scalable approach to CNN queries in a road network. Proceedings of VLDB, pages 865-876, Trondheim, Norway, 2005; Huang, Xuegang and Jensen, Christian S. and Saltenis, Simonas. The Island Approach to Nearest Neighbor Querying in Spatial Networks. Proceedings of SSTD, pages 33-40, Toronto, Canada, 2005; Ulrith Lauther. An Extremely Fast, Exact Algorithm for Finding Shortest Paths in Static Networks with Geographical Background. Geoinformation and Mobilitat, pages 33-40, Toronto, Canada, 2004; and Wagner, Dorothea and Willhalm, Thomas. Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs. Proceedings of Algorithms-ESA, 2003) to efficiently compute the distance and route between objects in large road networks.